#include <iostream>
#include <cstdlib>
#include <limits>

#define BLACK false
#define RED true
#define MIN (std::numeric_limits<T>::min())

template <typename T>
class Node
{
public:
	T max;
    T low;
    T high;
	Node<T>* lc;
	Node<T>* rc;
	Node<T>* parent;
    bool color = RED;
    Node(){parent = lc = rc = NULL;}
	Node(T _low, T _high);
    ~Node(){};
};

template <typename T>
class IntervalTree
{
private:
    void inorder_walk(Node<T>* _x) const;    //being changed
    void release(Node<T>* _x);    //delete one node
    void LeftRotate(Node<T>* _x);
    void RightRotate(Node<T>* _x);
    
    void rbinsert(Node<T>* _z);   //RBT, using rbinsertfixup         
    void rbinsertfixup(Node<T>* _z);    //RBT, for rbinsert
    void rbtransplant(Node<T>* u, Node<T>* v);
    void rbdelfixup(Node<T>* x);    //RBT, for rbdel
    
    T Max(T _x,T _y,T _z);
    Node<T>* Interval_Search(Node<T>* _i);   //zu jian
    
	Node<T>* root;
    Node<T>* nil;
    
public:
    IntervalTree();
    IntervalTree(T _data);
    ~IntervalTree();
    
    Node<T>* min(Node<T>* _x) const;
    Node<T>* max(Node<T>* _x) const;
    Node<T>* successor(Node<T>* _x) const;
    Node<T>* predecessor(Node<T>* _x) const;
    void inorder_walk() const;
    
    void rbinsert(T _low, T _high);    //IT jie kou    
	void rbdel(Node<T>* _z);    //RBT, using rbtransplant, rbdelfixup   
	
    Node<T>* Interval_Search(T _low,T _high);    //IT jie kou
    
};

//Node----------------------------------------------------
template <typename T>
Node<T>::Node(T _low, T _high)
{
    low = _low;
    high = _high;
    max = _high;
    parent = lc = rc = NULL;
};

//IntervalTree--private-----------------------------------
template <typename T>
void IntervalTree<T>::inorder_walk(Node<T>* _x) const
{
    if(_x != nil)
    {
		inorder_walk(_x->lc);
		std::cout << "(" << _x->low << "," << _x->high << ")" << _x->color << std::endl;
		inorder_walk(_x->rc);
    }
};

template <typename T>
void IntervalTree<T>::release(Node<T>* _x)
{
    if(_x != nil)
    {
		release(_x->lc);
		release(_x->rc);
		delete _x;
    }	
};

template <typename T>
void IntervalTree<T>::LeftRotate(Node<T>* _x)
{
    Node<T>* y = _x->rc;
    _x->rc = y->lc;
    if(y->lc != nil)
		y->lc->parent = _x;
    y->parent = _x->parent;
    if(_x->parent == nil)
		root = y;
    else if(_x == _x->parent->lc)
		_x->parent->lc = y;
    else
		_x->parent->rc = y;
    y->lc = _x;
    _x->parent = y;
    y->max = _x->max;
    _x->max = Max(_x->high,_x->lc->max,_x->rc->max);
};

template <typename T>
void IntervalTree<T>::RightRotate(Node<T>* _x)
{
    Node<T>* y = _x->lc;
    _x->lc = y->rc;
    if(y->rc != nil)
		y->rc->parent = _x;
    y->parent = _x->parent;
    if(_x->parent == nil)
		root = y;
    else if(_x == _x->parent->lc)
		_x->parent->lc = y;
    else
		_x->parent->rc = y;
    y->rc = _x;
    _x->parent = y;
    y->max = _x->max;
    _x->max = Max(_x->high, _x->lc->max, _x->rc->max);
};

template <typename T>
void IntervalTree<T>::rbinsert(Node<T>* _z)
{
    Node<T>* y;
    Node<T>* x;
    y = nil;
    x = root;
    while(x != nil)
    {
        y = x;
        if(_z->low < x->low)
        {
			if(_z->high > x->max) 
				x->max = _z->high;
			x = x->lc;
		}
        else
		{
			if(_z->high > x->max) 
				x->max = _z->high;
			x = x->rc;
		}
    }
    _z->parent = y;
    if(y == nil)
    	root = _z;
    else if(_z->low < y->low)
    {
		if(_z->high > y->max) 
			y->max = _z->high;
		y->lc = _z;
	}
    else 
	{
		if(_z->high > y->max) 
		y->max = _z->high;
		y->rc = _z;
	}
    _z->lc = nil;
    _z->rc = nil;
    _z->color = RED;
    rbinsertfixup(_z);
  
}

template <typename T>
void IntervalTree<T>::rbinsertfixup(Node<T>* _z)
{
    while(_z->parent->color == RED)
    if(_z->parent == _z->parent->parent->lc)
	{
	    Node<T>* y = _z->parent->parent->rc;
	    if(y->color == RED)
	    {
			_z->parent->color = y->color = BLACK;
			_z->parent->parent->color = RED;
			_z = _z->parent->parent;
	    }
	    else
	    {
			if(_z == _z->parent->rc)
			{
                _z = _z->parent;
		    	LeftRotate(_z);
			}
            _z->parent->color = BLACK;
            _z->parent->parent->color = RED;
			RightRotate(_z->parent->parent);
	    }
	}
    else 
	{
	    Node<T>* y = _z->parent->parent->lc;
	    if(y->color == RED)
	    {
			_z->parent->color = y->color = BLACK;
			_z->parent->parent->color = RED;
			_z = _z->parent->parent;
	    }
	    else
	    {
			if(_z == _z->parent->lc)
			{
                _z = _z->parent;
		    	RightRotate(_z);
			}
            _z->parent->color = BLACK;
            _z->parent->parent->color = RED;
			LeftRotate(_z->parent->parent);
	    }
	}
    root->color = BLACK;
}

template <typename T>
void IntervalTree<T>::rbtransplant(Node<T>* u, Node<T>* v)
{
    if(u->parent == nil)
        root = v;
    else if(u == u->parent->lc)
        u->parent->lc = v;
    else 
		u->parent->rc = v;
    v->parent = u->parent;
}

template <typename T>
void IntervalTree<T>::rbdelfixup(Node<T>* x)
{
    while (x != root && x->color == BLACK)
    	if(x == x->parent->lc)
    	{
    		Node<T>* w = x->parent->rc;
    		if(w->color == RED)
    		{
    			w->color = BLACK;
    			x->parent->color = RED;
    			LeftRotate(x->parent);
    			w = x->parent->rc;
    		}
    		if(w->lc->color == BLACK && w->rc->color == BLACK)
    		{
    		    w->color = RED;
    		    x = x->parent;
    		}
    		else
			{
		 	    if(w->rc->color == BLACK)
		 	    {
					w->lc->color = BLACK;
					w->color = RED;
					RightRotate(w);
					w = x->parent->rc;
			    }
			    w->color = x->parent->color;
			    x->parent->color = BLACK;
			    w->rc->color = BLACK;
			    LeftRotate(x->parent);
			    x = root;
			}
	    }
	    else
     	{
    		Node<T>* w = x->parent->lc;
    		if(w->color == RED)
    		{
    		    w->color = BLACK;
    		    x->parent->color = RED;
    		    RightRotate(x->parent);
    		    w = x->parent->lc;
    		}
    		if(w->rc->color == BLACK && w->lc->color == BLACK)
    		{
    		    w->color = RED;
    		    x = x->parent;
    		}
    		else
			{
		    	if(w->lc->color == BLACK)
		    	{
					w->rc->color = BLACK;
					w->color = RED;
					LeftRotate(w);
					w = x->parent->lc;
		   		}
		    	w->color = x->parent->color;
		    	x->parent->color = BLACK;
		    	w->lc->color = BLACK;
		    	RightRotate(x->parent);
		    	x = root;
			}
     	}
    x->color = BLACK;   
}

template <typename T>
T IntervalTree<T>::Max(T _x,T _y,T _z)
{   
	if(_x >= _y && _x >= _z) 
		return _x;
    else if(_y >= _x && _y >= _z) 
		return _y;
    else 
		return _z;
}

template <typename T>
Node<T>* IntervalTree<T>::Interval_Search(Node<T>* _i)
{
    Node<T>* x;
    x = root;
    while(x != nil && (_i->low > x->high || _i->high < x->low))
    {
        if(x->lc != nil && x->lc->max >= _i->low)
            x = x->lc;
        else x = x->rc;
    }
    return x;
} 

//IntervalTree--public------------------------------------

template <typename T>
IntervalTree<T>::IntervalTree()
{
	nil = new Node<T>;
	nil->color = BLACK;
	nil->max = MIN;
	root = nil;
}

template <typename T>
IntervalTree<T>::~IntervalTree()
{
    release(root);
    delete nil;
};

template <typename T>
Node<T>* IntervalTree<T>::min(Node<T>* _x) const
{
    while (_x->lc != nil)
		_x = _x->lc;
    return _x;
};

template <typename T>
Node<T>* IntervalTree<T>::max(Node<T>* _x) const
{
    while (_x->rc != nil)
		_x = _x->rc;
    return _x;
};

template <typename T>
Node<T>* IntervalTree<T>::successor(Node<T>* _x) const
{
    Node<T>* x = _x;
    if(x->rc != nil)
	return min(x->rc);
    Node<T>* y = x->parent;
    while (y != nil && x == y->rc)
    {
		x = y;
		y = y->parent;
    }
    return y;
};

template <typename T>
Node<T>* IntervalTree<T>::predecessor(Node<T>* _x) const
{
    Node<T>* x = _x;
    if(x->lc != nil)
        return max(x->lc);
    Node<T>* y = x->parent;
    while(y != nil && x == y->lc)
    {
       x = y;
       y = y->parent;
    }
    return y;
};

template <typename T>
void IntervalTree<T>::inorder_walk() const
{
    inorder_walk(root);
    std::cout << std::endl;
};

template <typename T>
void IntervalTree<T>::rbinsert(T _low, T _high)
{
    Node<T>* x = new Node<T>(_low, _high);
    rbinsert(x);
}

template <typename T>
void IntervalTree<T>::rbdel(Node<T>* _z)
{
    Node<T>* y = _z;
    bool original_color_y = y->color;
    Node<T>* x;
    if(_z->lc == nil)
    {
		x = _z->rc;
		rbtransplant(_z, _z->rc);
    }
    else if(_z->rc == nil)
    {
		x = _z->lc;
		rbtransplant(_z, _z->lc);
    }
    else
    {
    	y = min(_z->rc);
    	original_color_y = y->color;
    	x = y->rc;
		if(y->parent != _z)
    	{
    	    rbtransplant(y, y->rc);
    	    y->rc = _z->rc;
    	    y->rc->parent = y;
    	}
    	rbtransplant(_z, y);
    	y->lc = _z->lc;
    	y->lc->parent = y;
    	y->color = _z->color;
    }
    if(original_color_y == BLACK)
     	rbdelfixup(x);
}

template <typename T>
Node<T>* IntervalTree<T>::Interval_Search(T _low,T _high)
{
    Node<T>* x = new Node<T>(_low,_high);
    Interval_Search(x);
}
//other---------------------------------------------------







